package leetcode.Fiftyone_to_One_hundred;

/**
 * 删除排序链表中的重复元素 II
 *
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 中击败了98.69% 的用户
 */
public class Test82 {

   static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    // 给定的是排序链表

    /**
     * 三指针法：快慢两根指针 + 记录慢指针前驱节点的指针
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;
        ListNode slow = node.next;
        ListNode fast = node.next.next;
        while (fast != null && fast.next != null) {
            if (fast != null && slow != null && fast.val != slow.val) {
                if (pre != slow) {
                    pre = pre.next;
                }
                fast = fast.next;
                slow = slow.next;
            } else {
                // if find fast equals slow. stay pre and slow move fast to the first that
                // not equals slow
                while (fast != null && slow != null && fast.val == slow.val) {
                    fast = fast.next;
                }
                // 现在 fast 指向4，slow 指向3.将pre的next指向fast即可
                pre.next = fast;
                slow = pre;
            }
        }
        if (fast != null && slow != null && slow.val == fast.val ) {
            while (fast != null && slow != null && fast.val == slow.val) {
                fast = fast.next;
            }
            // 现在 fast 指向4，slow 指向3.将pre的next指向fast即可
            pre.next = fast;
            slow = pre;
        }
        return node.next;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(1);
//        ListNode l4 = new ListNode(2);
//        ListNode l5 = new ListNode(3);
//        ListNode l6 = new ListNode(4);
//        ListNode l7 = new ListNode(5);

        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;
//        l5.next = l6;
//        l6.next = l7;
        ListNode node = deleteDuplicates(l1);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

}
